The invention relates generally to computing apparatus and methods and in particular to a method and apparatus for storing machine instructions and for detecting and correcting an instruction cache miss in a data processing system.
In an apparatus which uses a very long instruction word (VLIW) such as that employed in implementing a Trace Scheduling method and which has an instruction word length of over 1,000 bits, a major architectural consideration is the massive storage and bandwidth demands of the system. Storage is required for the instructions themselves and the bandwidth is required to direct the instruction data at high bit rates, to where it is needed during each cycle of operation. Typical data processing systems employ an instruction cache to increase the processor throughput, and it is expected that, in theory, most instructions in a sequence will be stored in the instruction cache memory which operates at a very high access rate, typically on the order of thirty nanoseconds in present day apparatus.
Traditionally, designers of wide instruction word computers have dealt with the problem of bandwidth through compromise, and therefore, have limited the instruction word width. A primary technique for limiting the word width attempts to anticipate which individual instructions will typically be combined in a single long instruction and provides compact instruction encodings for those cases, but only those cases. Such guesses, in our experience, prove almost universally to be wrong. Consequently processors are built that, even in the inner loops of a program where substantial parallelism is available, achieve only a small portion of their potential performance (without use of exhaustive hand coding). Thus, requiring a compiler to find and use the "patterns," that the machine designer guessed would be used, simply does not work.
It is also important in such apparatus to provide for a high speed mechanism to fill instruction cache memory should an instruction not be present. This process is relatively simple when the instructions are being loaded from a known, fixed format memory. In accordance with the present invention, however, in order to save memory space, a variable length memory format is employed which requires substantial computation and cataloging in order to refill the cache memory at a significant high data rate. The development of a corresponding high speed cache refill mechanism when the original instruction data has a variable length structure, is quite difficult.
An object of the invention is therefore an instruction storage and cache miss recovery method and apparatus, for a very long instruction word, which reduces or minimizes the main storage requirements for the very long instruction word. Other objects of the invention are a method and apparatus for enabling high speed, reliable refill of a fixed word length instruction cache from a variable length instruction memory storage. Further objects of the invention are a parallel processing multiprocessor system having a very long instruction word which reliably and at high speed implements a cache miss engine for filling a distributed instruction cache.